package Solutions

import "sort"

func maxStarSum(vals []int, edges [][]int, k int) int {
	l := len(edges)
	ans := -(1<<63 - 1)
	for _, v := range vals {
		if v > ans {
			ans = v
		}
	}
	for i := 0; i < l; i++ {
		edges = append(edges, []int{edges[i][1], edges[i][0]})
	}
	sort.Slice(edges, func(i, j int) bool {
		if edges[i][0] == edges[j][0] {
			return vals[edges[i][1]] > vals[edges[j][1]]
		} else {
			return edges[i][0] < edges[j][0]
		}
	})

	for i := 0; i < len(edges); {
		p := edges[i][0]
		tem := vals[p]
		for j := 0; j < k && i+j < len(edges) && edges[i+j][0] == p; j++ {
			if vals[edges[i+j][1]] > 0 {
				tem += vals[edges[i+j][1]]
			} else {
				break
			}
		}
		if tem > ans {
			ans = tem
		}
		for ; i < len(edges) && edges[i][0] == p; i++ {
		}
	}
	return ans
}
